package practice;

/**
 * @Author Yi Jun jie
 * @Date 2021/3/8 15:16
 * 用最少的 2, 5, 7 硬币整找 27元，最少要多少个
 */
public class FBDemo {
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{2, 5, 7}, 27));
    }

    public static int coinChange(int A[], int M) {
        int[] f = new int[M + 1];//开辟数组用来存每个状态的值
        f[0] = 0;
        for (int i = 1; i <= M; i++) {
            f[i] = Integer.MAX_VALUE;//初始化数组值为正无穷
            for(int j = 0; j < A.length; j++) {
                //保证参数的值 > 0 同时保证次参数对应的函数的值不是正无穷
                //比如 f[x - 2] 之中：x - 2 > 0 并且 f[x - 2] > 0
                if(i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i], f[i - A[j]] + 1);
                }
            }
        }
        if(f[M] == Integer.MAX_VALUE) {
            return -1;
        }
        return f[M];
    }
}
